package two.prefixSum_difference;

/**
 * 二维区域和检索 - 矩阵不可变
 * 二维前缀和代码模板
 */
public class NumMatrix {

    //思路：二维前缀和
    //时间复杂度：预处理O(n^2)；访问：O(n)
    private int[][] S;
    private int get_S(int i, int j){ //处理下标，防止越界
        if(i >= 0 && j >= 0) return S[i][j];
        return 0;
    }

    public NumMatrix(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        S = new int[row][col];
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                // S[i][j] = S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1] + matrix[i][i];
                S[i][j] = get_S(i, j - 1) + get_S(i - 1, j) - get_S(i - 1, j - 1) + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        // return S[row2][col2] - S[row2][col1 - 1] - S[row1 - 1][col2] + S[row1 - 1][col1 - 1];
        return get_S(row2, col2) - get_S(row2, col1 - 1) - get_S(row1 - 1, col2) + get_S(row1 - 1, col1 - 1);
    }
}
